{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Course Schedule III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: scheduleCourse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #课程表 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这里有 <code>n</code> 门不同的在线课程，按从 <code>1</code> 到 <code>n</code>&nbsp;编号。给你一个数组 <code>courses</code> ，其中 <code>courses[i] = [duration<sub>i</sub>, lastDay<sub>i</sub>]</code> 表示第 <code>i</code> 门课将会 <strong>持续</strong> 上 <code>duration<sub>i</sub></code> 天课，并且必须在不晚于 <code>lastDay<sub>i</sub></code> 的时候完成。</p>\n",
    "\n",
    "<p>你的学期从第 <code>1</code> 天开始。且不能同时修读两门及两门以上的课程。</p>\n",
    "\n",
    "<p>返回你最多可以修读的课程数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "这里一共有 4 门课程，但是你最多可以修 3 门：\n",
    "首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。\n",
    "第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。\n",
    "第三，修第 2 门课，耗时 200 天，在第 1300 天完成。\n",
    "第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>courses = [[1,2]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>courses = [[3,2],[4,3]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= courses.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= duration<sub>i</sub>, lastDay<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [course-schedule-iii](https://leetcode.cn/problems/course-schedule-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [course-schedule-iii](https://leetcode.cn/problems/course-schedule-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[100,200],[200,1300],[1000,1250],[2000,3200]]', '[[1,2]]', '[[3,2],[4,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda ele: ele[1], reverse=True)\n",
    "        i, day_sum, big_heap = 0, 0, []\n",
    "        def up_fliter(heap, e, i):\n",
    "            heap.append(e)\n",
    "            while i != 0:\n",
    "                root_ind = (i - 1) // 2 if i % 2 else (i - 2) // 2\n",
    "                if heap[i] > heap[root_ind]:\n",
    "                    heap[i], heap[root_ind] = heap[root_ind], heap[i]\n",
    "                    i = root_ind\n",
    "                else: break\n",
    "            return heap\n",
    "        def down_pop(heap):\n",
    "            heap_len = len(heap) - 1\n",
    "            heap[0], i = heap[-1], 0\n",
    "            while i < heap_len:\n",
    "                left, right = 2 * i + 1, 2 * i + 2\n",
    "                if left < heap_len:\n",
    "                    if right < heap_len and heap[right] > heap[left]:\n",
    "                        left = right\n",
    "                    if heap[i] < heap[left]:\n",
    "                        heap[i], heap[left], i = heap[left], heap[i], left\n",
    "                    else: break\n",
    "                else: break\n",
    "            return heap[: -1]\n",
    "        while courses:\n",
    "            temp = courses.pop()\n",
    "            big_heap = up_fliter(big_heap, temp[0], i)\n",
    "            day_sum += temp[0]\n",
    "            if day_sum <= temp[1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                day_sum -= big_heap[0]\n",
    "                big_heap = down_pop(big_heap)\n",
    "\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        # print(courses)\n",
    "        ti = 0\n",
    "        h = []\n",
    "        for st, ed in courses:\n",
    "            ti += st\n",
    "            heapq.heappush(h, -st)\n",
    "            if ti > ed:\n",
    "                ti += heapq.heappop(h)\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: c[1])\n",
    "\n",
    "        q = list()\n",
    "        # 优先队列中所有课程的总时间\n",
    "        total = 0\n",
    "\n",
    "        for ti, di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                # Python 默认是小根堆\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "\n",
    "        return len(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "\n",
    "        q, total = [], 0\n",
    "        for di,li in courses:\n",
    "            if total + di <= li:\n",
    "                total += di\n",
    "                heapq.heappush(q, -di)\n",
    "            elif q and -q[0] > di:\n",
    "                total += heapq.heappop(q) + di\n",
    "                heapq.heappush(q, -di)\n",
    "\n",
    "        return len(q)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        heap = []\n",
    "        cur_time = 0\n",
    "        for duration, last_day in courses:\n",
    "            if cur_time + duration <= last_day:\n",
    "                heapq.heappush(heap, -duration)\n",
    "                cur_time += duration\n",
    "            elif heap:\n",
    "                learned_max_duration = heapq.heappop(heap)\n",
    "                if duration < -learned_max_duration:\n",
    "                    heapq.heappush(heap, -duration)\n",
    "                    cur_time += (learned_max_duration + duration)\n",
    "                else:\n",
    "                    heapq.heappush(heap, learned_max_duration)\n",
    "        return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        a=[]\n",
    "        t=0\n",
    "        courses=sorted(courses, key=lambda x: x[1])\n",
    "        for i in courses:\n",
    "            \n",
    "            if t+i[0]>i[1] and a and -a[0]>i[0] :\n",
    "                \n",
    "                t=t+heapq.heappop(a)\n",
    "            if t+i[0]<=i[1]:\n",
    "                heapq.heappush(a,-i[0])\n",
    "                t=t+i[0]\n",
    "\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key = lambda c:c[1])\n",
    "        total = 0\n",
    "        q = list()\n",
    "        for ti,di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                heapq.heappush(q,-ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q,-ti)\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        a=[]\n",
    "        t=0\n",
    "        courses=sorted(courses, key=lambda x: x[1])\n",
    "        for i in courses:\n",
    "            \n",
    "            if t+i[0]>i[1] and a and -a[0]>i[0] :\n",
    "                t=t+heapq.heappop(a)\n",
    "            if t+i[0]<=i[1]:\n",
    "                heapq.heappush(a,-i[0])\n",
    "                t=t+i[0]\n",
    "\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses = sorted(courses, key=lambda x:x[1])\n",
    "        timestamp, heap = 0, []\n",
    "        for c in courses:\n",
    "            if timestamp + c[0] <= c[1]:\n",
    "                heapq.heappush(heap, -c[0])\n",
    "                timestamp += c[0]\n",
    "            else:\n",
    "                if heap and c[0] < -heap[0]:\n",
    "                    timestamp += heapq.heappop(heap)\n",
    "                    heapq.heappush(heap, -c[0])\n",
    "                    timestamp += c[0]\n",
    "        return len(heap) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        a=[]\n",
    "        t=0\n",
    "        courses=sorted(courses, key=lambda x: x[1])\n",
    "        for i in courses:\n",
    "            \n",
    "            if t+i[0]<=i[1]:\n",
    "                heapq.heappush(a,-i[0])\n",
    "                t=t+i[0]\n",
    "            elif t+i[0]>i[1] and a and -a[0]>i[0] :\n",
    "                t=t+a[0]+i[0]\n",
    "                heapq.heappop(a)\n",
    "                heapq.heappush(a,-i[0])\n",
    "\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        pq, t = [], 0\n",
    "        for duration, lastDay in sorted(courses, key=lambda x:x[1]):\n",
    "            if t + duration > lastDay and pq and -pq[0] > duration:\n",
    "                t += heapq.heappop(pq)\n",
    "            if t + duration <= lastDay:\n",
    "                heapq.heappush(pq, -duration)\n",
    "                t += duration\n",
    "        return len(pq)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\r\n",
    "        courses.sort(key = lambda c: c[1])\r\n",
    "        q = list()\r\n",
    "        total = 0\r\n",
    "        for ti, di in courses:\r\n",
    "            if total + ti <= di:\r\n",
    "                total += ti\r\n",
    "                heapq.heappush(q, -ti) # python里是默认小根堆\r\n",
    "            elif q and -q[0] > ti:\r\n",
    "                total -= -q[0] - ti\r\n",
    "                heapq.heappop(q)\r\n",
    "                heapq.heappush(q, -ti)\r\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses_new = sorted(courses, key=lambda x:x[1])\n",
    "        \n",
    "        pri_queue = PriorityQueue()\n",
    "        now_count = 0\n",
    "        now_time = 0\n",
    "        for each_courses_new in courses_new:\n",
    "            if now_time + each_courses_new[0] <= each_courses_new[1]:\n",
    "                now_count += 1\n",
    "                now_time += each_courses_new[0]\n",
    "                pri_queue.put((-each_courses_new[0]))\n",
    "            else:\n",
    "                if pri_queue.qsize():\n",
    "                # 判断这个新的课程的时间是不是最长的，如果是最长的，则不处理， 如果不是最长的，则不修最长的，修现在这门课程\n",
    "                    course_max_time = - pri_queue.get()\n",
    "                    if course_max_time > each_courses_new[0]:\n",
    "                        pri_queue.put(-each_courses_new[0])\n",
    "                        now_time += each_courses_new[0] - course_max_time\n",
    "                    else:\n",
    "                        pri_queue.put(-course_max_time)\n",
    "\n",
    "\n",
    "        \n",
    "        return now_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        t, pq = 0, []\n",
    "        for i, j in sorted(courses, key=lambda it:it[1]):\n",
    "            t += i\n",
    "            if t > j:\n",
    "                t += heappushpop(pq, -i)\n",
    "            else:\n",
    "                heappush(pq, -i)\n",
    "        return len(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses_new = sorted(courses, key=lambda x:x[1])\n",
    "        \n",
    "        pri_queue = PriorityQueue()\n",
    "        now_count = 0\n",
    "        now_time = 0\n",
    "        for each_courses_new in courses_new:\n",
    "            if now_time + each_courses_new[0] <= each_courses_new[1]:\n",
    "                now_count += 1\n",
    "                now_time += each_courses_new[0]\n",
    "                pri_queue.put((-each_courses_new[0]))\n",
    "            else:\n",
    "                if pri_queue.qsize():\n",
    "                # 判断这个新的课程的时间是不是最长的，如果是最长的，则不处理， 如果不是最长的，则不修最长的，修现在这门课程\n",
    "                    course_max_time = - pri_queue.get()\n",
    "                    if course_max_time > each_courses_new[0]:\n",
    "                        pri_queue.put(-each_courses_new[0])\n",
    "                        now_time += each_courses_new[0] - course_max_time\n",
    "                    else:\n",
    "                        pri_queue.put(-course_max_time)\n",
    "\n",
    "\n",
    "        \n",
    "        return now_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        print(courses)\n",
    "        ti = 0\n",
    "        h = []\n",
    "        for st, ed in courses:\n",
    "            ti += st\n",
    "            heapq.heappush(h, -st)\n",
    "            if ti > ed:\n",
    "                ti += heapq.heappop(h)\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses_new = sorted(courses, key=lambda x:x[1])\n",
    "        \n",
    "        pri_queue = PriorityQueue()\n",
    "        now_count = 0\n",
    "        now_time = 0\n",
    "        for each_courses_new in courses_new:\n",
    "            if now_time + each_courses_new[0] <= each_courses_new[1]:\n",
    "                now_count += 1\n",
    "                now_time += each_courses_new[0]\n",
    "                pri_queue.put((-each_courses_new[0]))\n",
    "            else:\n",
    "                if pri_queue.qsize():\n",
    "                # 判断这个新的课程的时间是不是最长的，如果是最长的，则不处理， 如果不是最长的，则不修最长的，修现在这门课程\n",
    "                    course_max_time = - pri_queue.get()\n",
    "                    if course_max_time > each_courses_new[0]:\n",
    "                        pri_queue.put(-each_courses_new[0])\n",
    "                        now_time += each_courses_new[0] - course_max_time\n",
    "                    else:\n",
    "                        pri_queue.put(-course_max_time)\n",
    "\n",
    "\n",
    "        \n",
    "        return now_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        pq,t = [] , 0\n",
    "        for d,l in sorted(courses,key=lambda x:x[1]):\n",
    "            if t + d > l and pq and -pq[0] > d:\n",
    "                t += heapq.heappop(pq)\n",
    "            if t + d <= l:\n",
    "                heapq.heappush(pq,-d)\n",
    "                t += d\n",
    "        return len(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        q = []\n",
    "        for course in courses:\n",
    "            if course[0]>course[1]:\n",
    "                continue\n",
    "            cur+=course[0]\n",
    "            if cur<=course[1]:\n",
    "                heapq.heappush(q,(-course[0],course[1]))\n",
    "            else:\n",
    "                if -q[0][0]>course[0]:\n",
    "                    c = heapq.heappop(q)\n",
    "                    cur+=c[0]\n",
    "                    heapq.heappush(q, (-course[0],course[1]))\n",
    "                else:\n",
    "                    cur -= course[0]\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses_new = sorted(courses, key=lambda x:x[1])\n",
    "        \n",
    "        pri_queue = PriorityQueue()\n",
    "        now_count = 0\n",
    "        now_time = 0\n",
    "        for each_courses_new in courses_new:\n",
    "            if now_time + each_courses_new[0] <= each_courses_new[1]:\n",
    "                now_count += 1\n",
    "                now_time += each_courses_new[0]\n",
    "                pri_queue.put((-each_courses_new[0]))\n",
    "            else:\n",
    "                if pri_queue.qsize():\n",
    "                # 判断这个新的课程的时间是不是最长的，如果是最长的，则不处理， 如果不是最长的，则不修最长的，修现在这门课程\n",
    "                    course_max_time = - pri_queue.get()\n",
    "                    if course_max_time > each_courses_new[0]:\n",
    "                        pri_queue.put(-each_courses_new[0])\n",
    "                        now_time += each_courses_new[0] - course_max_time\n",
    "                    else:\n",
    "                        pri_queue.put(-course_max_time)\n",
    "\n",
    "\n",
    "        \n",
    "        return now_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(reverse = True,key = lambda x:x[1])\n",
    "        q = []\n",
    "        total = 0\n",
    "\n",
    "        while courses:\n",
    "            a,b = courses.pop()\n",
    "            if total + a <= b:\n",
    "                total += a\n",
    "                heappush(q,-a)\n",
    "            elif q and -q[0] > a:\n",
    "                total -= -q[0] - a\n",
    "                heappop(q)\n",
    "                heappush(q, -a)\n",
    "        \n",
    "        return len(q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        total = 0\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        class Data():\n",
    "            def __init__(self, x):\n",
    "                self.vals = [x]\n",
    "            def __lt__(self, other):\n",
    "                return self.vals[0]>=other.vals[0]\n",
    "            def __getitem__(self, ind):\n",
    "                return self.vals[ind]\n",
    "            def __len__(self):\n",
    "                return 1\n",
    "            def __repr__(self):\n",
    "                return self.vals.__repr__()\n",
    "        q = []\n",
    "        for ti,di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                heapq.heappush(q, Data(ti))\n",
    "            elif q and q[0][0] > ti:\n",
    "                total -= q[0][0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, Data(ti))\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        res, cur = 0, 0 \n",
    "        pq = []\n",
    "        for t, d in courses:\n",
    "            if cur + t <= d:\n",
    "                res += 1 \n",
    "                cur += t\n",
    "                heapq.heappush(pq, (-t, d))\n",
    "            elif pq and abs(pq[0][0]) > t:\n",
    "                tt, dd = heapq.heappop(pq)\n",
    "                cur += tt \n",
    "                cur += t \n",
    "                heapq.heappush(pq, (-t, d))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        class Course:\n",
    "            def __init__(self, i):\n",
    "                self.i = i\n",
    "                self.duration = courses[i][0]\n",
    "                self.deadline = courses[i][1]\n",
    "            def __lt__(self, other):\n",
    "                return self.duration > other.duration\n",
    "        # print(courses)\n",
    "        ans = []\n",
    "        totalTime = 0\n",
    "        for i, course in enumerate(courses):\n",
    "            if course[1]<course[0]:\n",
    "                continue\n",
    "            totalTime += course[0]\n",
    "            if totalTime > course[1]:\n",
    "                if ans[0].duration < course[0]:\n",
    "                    totalTime -= course[0]\n",
    "                    continue\n",
    "                totalTime -= courses[ans[0].i][0]\n",
    "                heapq.heapreplace(ans, Course(i))\n",
    "            else:\n",
    "                heapq.heappush(ans, Course(i))\n",
    "            # print(ans, totalTime)\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda ele: ele[1], reverse=True)\n",
    "        i, day_sum, big_heap = 0, 0, []\n",
    "        def up_fliter(heap, e, i):\n",
    "            heap.append(e)\n",
    "            while i != 0:\n",
    "                root_ind = (i - 1) // 2 if i % 2 else (i - 2) // 2\n",
    "                if heap[i] > heap[root_ind]:\n",
    "                    heap[i], heap[root_ind] = heap[root_ind], heap[i]\n",
    "                    i = root_ind\n",
    "                else: break\n",
    "            return heap\n",
    "        def down_pop(heap):\n",
    "            heap_len = len(heap) - 1\n",
    "            heap[0], i = heap[-1], 0\n",
    "            while i < heap_len:\n",
    "                left, right = 2 * i + 1, 2 * i + 2\n",
    "                if left < heap_len:\n",
    "                    if right < heap_len and heap[right] > heap[left]:\n",
    "                        left = right\n",
    "                    if heap[i] < heap[left]:\n",
    "                        heap[i], heap[left], i = heap[left], heap[i], left\n",
    "                    else: break\n",
    "                else: break\n",
    "            return heap[: -1]\n",
    "        while courses:\n",
    "            temp = courses.pop()\n",
    "            big_heap = up_fliter(big_heap, temp[0], i)\n",
    "            day_sum += temp[0]\n",
    "            if day_sum <= temp[1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                day_sum -= big_heap[0]\n",
    "                big_heap = down_pop(big_heap)\n",
    "\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        a = []\n",
    "        for i in courses:\n",
    "            if i[1] < i[0]:\n",
    "                continue\n",
    "            a.append(i[1])\n",
    "            d[i[1]].append(i[0])\n",
    "        a = sorted(list(set(a)))\n",
    "\n",
    "        now = 0\n",
    "        ans = 0\n",
    "        b = [0]\n",
    "        while a:\n",
    "            endtime = a.pop(0)\n",
    "            spendtime = d[endtime]\n",
    "            spendtime.sort()\n",
    "            for i in spendtime:\n",
    "                if now + i <= endtime:\n",
    "                    now += i\n",
    "                    ans += 1\n",
    "                    heapq.heappush(b, -i)\n",
    "                else:\n",
    "                    if -b[0] > i and now + b[0] + i <= endtime:\n",
    "                        now += b[0] + i\n",
    "                        heapq.heappop(b)\n",
    "                        heapq.heappush(b, -i)\n",
    "                    else:\n",
    "                        continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        q = []\n",
    "\n",
    "        end = 0\n",
    "        cnt = 0\n",
    "        for course in courses:\n",
    "            if course[0] + end <= course[1]:\n",
    "                end += course[0]\n",
    "                heapq.heappush(q, (-course[0], course[1]))\n",
    "                cnt += 1\n",
    "            elif q and -q[0][0] > course[0]:\n",
    "                long_course = heapq.heappop(q)\n",
    "                heapq.heappush(q, (-course[0], course[1]))\n",
    "                end -= -long_course[0] - course[0]\n",
    "\n",
    "        return cnt        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # 将课程按ddl从后往前排序\n",
    "        courses.sort(key=lambda x:-x[1])\n",
    "        # print(courses)\n",
    "\n",
    "        ans = 0\n",
    "        # 最小堆，存[duration]\n",
    "        heap = []\n",
    "        # 取出ddl最晚的课（一门或多门）\n",
    "        while courses:\n",
    "            ddl1 = courses[0][1]\n",
    "            while courses and courses[0][1]==ddl1:\n",
    "                course = courses.pop(0)\n",
    "                # 剔除不可能上完的\n",
    "                if course[0]>course[1]:\n",
    "                    continue\n",
    "                # 将duration存入最小堆\n",
    "                heappush(heap, course[0])\n",
    "            # 找到第二晚的ddl\n",
    "            if courses:\n",
    "                ddl2 = courses[0][1]\n",
    "            else:\n",
    "                ddl2 = 0\n",
    "            # print(f\"ddl2-1 {ddl2}-{ddl1}\")\n",
    "            # print(f\"c_ddl1 {heap}\")\n",
    "            # 在这段时间内，能上完的课先上完\n",
    "            time_left = ddl1-ddl2\n",
    "            while heap:\n",
    "                duration = heappop(heap)\n",
    "                if time_left>=duration:\n",
    "                    # print(f\"added duration {duration}\")\n",
    "                    ans += 1\n",
    "                    time_left -= duration\n",
    "                else:\n",
    "                    # 可能有一门或多门无法上完\n",
    "                    # 第一门减去可以上的时间，重新存入\n",
    "                    duration -= time_left\n",
    "                    # print(f\"push new duration {duration}\")\n",
    "                    heappush(heap, duration)\n",
    "                    # 剩下的课留在堆中即可\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda ele: ele[1], reverse=True)\n",
    "        i, day_sum, big_heap = 0, 0, []\n",
    "        def up_fliter(heap, e, i):\n",
    "            heap.append(e)\n",
    "            while i != 0:\n",
    "                root_ind = (i - 1) // 2 if i % 2 else (i - 2) // 2\n",
    "                if heap[i] > heap[root_ind]:\n",
    "                    heap[i], heap[root_ind] = heap[root_ind], heap[i]\n",
    "                    i = root_ind\n",
    "                else: break\n",
    "            return heap\n",
    "        def down_fliter(heap, e, heap_len):\n",
    "            i, heap[0] = 0, e\n",
    "            while i < heap_len:\n",
    "                left, right = 2 * i + 1, 2 * i + 2\n",
    "                if left < heap_len:\n",
    "                    if right < heap_len and heap[right] > heap[left]:\n",
    "                        left = right\n",
    "                    if heap[i] < heap[left]:\n",
    "                        heap[i], heap[left], i = heap[left], heap[i], left\n",
    "                    else: return heap\n",
    "                else: return heap\n",
    "            return heap\n",
    "        while courses:\n",
    "            temp = courses.pop()\n",
    "            day_sum += temp[0]\n",
    "            if day_sum <= temp[1]:\n",
    "                big_heap = up_fliter(big_heap, temp[0], i)\n",
    "                i += 1\n",
    "            else:\n",
    "                if not big_heap or temp[0] >= big_heap[0]:\n",
    "                    day_sum -= temp[0]\n",
    "                else:\n",
    "                    day_sum -= big_heap[0]\n",
    "                    big_heap = down_fliter(big_heap, temp[0], i)\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]\n",
    "        :param courses:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        sd1 = SortedList()\n",
    "\n",
    "        total = 0\n",
    "\n",
    "        for i in courses:\n",
    "            if total + i[0] <= i[1]:\n",
    "                total += i[0]\n",
    "                sd1.add(i[0])\n",
    "            else:\n",
    "                if len(sd1) > 0 and sd1[-1] > i[0]:\n",
    "                    total -= sd1[-1] - i[0]\n",
    "                    sd1.pop()\n",
    "                    sd1.add(i[0])\n",
    "        return len(sd1)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.scheduleCourse(  [[5,5],[4,6],[2,6]] ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        ans=0\n",
    "        sl=SortedList()\n",
    "        s=0\n",
    "        for a,b in courses:\n",
    "            sl.add(a)\n",
    "            s+=a \n",
    "            if s>b:\n",
    "                s-=sl.pop()\n",
    "            ans=max(ans,len(sl))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        q = []\n",
    "\n",
    "        end = 0\n",
    "        cnt = 0\n",
    "        for course in courses:\n",
    "            if course[0] + end <= course[1]:\n",
    "                end += course[0]\n",
    "                heapq.heappush(q, (-course[0], course[1]))\n",
    "                cnt += 1\n",
    "            elif q and -q[0][0] > course[0]:\n",
    "                long_course = heapq.heappop(q)\n",
    "                heapq.heappush(q, (-course[0], course[1]))\n",
    "                end -= -long_course[0] - course[0]\n",
    "\n",
    "        return cnt        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        print(courses)\n",
    "        ti = 0\n",
    "        h = []\n",
    "        # for st, ed in courses:\n",
    "        #     ti += st\n",
    "        #     heapq.heappush(h, -st)\n",
    "        #     if ti > ed:\n",
    "        #         print(\"h\",h)\n",
    "        #         a= heapq.heappop(h)\n",
    "        #         print(\"pop\",a)\n",
    "        #         ti += a\n",
    "        for st,ed in courses:\n",
    "            ti +=st\n",
    "            h.append(st)\n",
    "            if ti>ed:\n",
    "                h=sorted(h)\n",
    "                ti+= -h.pop()\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "\n",
    "        deadline = 0\n",
    "\n",
    "        heap = []\n",
    "\n",
    "        for course in courses:\n",
    "            deadline += course[0]\n",
    "            heapq.heappush(heap, -course[0])\n",
    "\n",
    "            if deadline > course[1]:\n",
    "                deadline += heapq.heappop(heap)\n",
    "        \n",
    "        return len(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key = lambda x : x[1])\n",
    "        cnt, heap = 0, []\n",
    "        for c in courses:\n",
    "            if cnt + c[0] <= c[1]:\n",
    "                heapq.heappush(heap, -1 * c[0])\n",
    "                cnt += c[0]\n",
    "            elif heap:\n",
    "                maxVal = -1 * heapq.heappop(heap)\n",
    "                heapq.heappush(heap, -1 * min(c[0], maxVal))\n",
    "                cnt = cnt - maxVal + min(c[0], maxVal)\n",
    "        return len(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]\n",
    "        :param courses:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        sd1 = SortedList()\n",
    "\n",
    "        total = 0\n",
    "\n",
    "        for i in courses:\n",
    "            if total + i[0] <= i[1]:\n",
    "                total += i[0]\n",
    "                sd1.add(i[0])\n",
    "            else:\n",
    "                if len(sd1) > 0 and sd1[-1] > i[0]:\n",
    "                    total -= sd1[-1] - i[0]\n",
    "                    sd1.pop()\n",
    "                    sd1.add(i[0])\n",
    "        return len(sd1)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.scheduleCourse(  [[5,5],[4,6],[2,6]] ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: c[1])\n",
    "\n",
    "        q = list()\n",
    "        # 优先队列中所有课程的总时间\n",
    "        total = 0\n",
    "\n",
    "        for ti, di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                # Python 默认是小根堆\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "\n",
    "        return len(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:[x[1],x[0]])\n",
    "        learned = SortedList()\n",
    "        lastday = 0\n",
    "        for c in courses:\n",
    "            nextday = lastday+c[0]\n",
    "            if nextday<=c[1]:\n",
    "                lastday=nextday\n",
    "                learned.add(c[0])\n",
    "            else:\n",
    "                if learned and learned[-1]>c[0]:\n",
    "                    lastday = lastday-learned[-1]+c[0]\n",
    "                    learned.pop()\n",
    "                    learned.add(c[0])\n",
    "        return len(learned)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(99999)\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        for d, b in courses:\n",
    "            a = b - d + 1\n",
    "            if a < 1:\n",
    "                continue\n",
    "\n",
    "            arr.append( (b, a, d) )\n",
    "\n",
    "        arr.sort()\n",
    "\n",
    "        que = PriorityQueue()\n",
    "\n",
    "        t = 1\n",
    "        cnt = 0\n",
    "        for b, a, d in arr:\n",
    "            if a >= t:\n",
    "                t += d\n",
    "                cnt += 1\n",
    "                que.put( (-d, a, d) )\n",
    "\n",
    "            else:\n",
    "\n",
    "                _, aa, dd = que.get()\n",
    "                if d < dd and a >= t - dd:\n",
    "                    t -= dd\n",
    "                    t += d\n",
    "                    que.put( (-d, a, d) )\n",
    "\n",
    "                    # if aa >= t:\n",
    "                    #     cnt += 1\n",
    "                    #     t += dd\n",
    "                    #     que.put( (-dd, aa, dd) )\n",
    "\n",
    "\n",
    "                else:\n",
    "                    que.put( (-dd, aa, dd) )\n",
    "\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        time=0\n",
    "        heap=[]\n",
    "        for course in courses:\n",
    "            time+=course[0]\n",
    "            heapq.heappush(heap,-course[0])\n",
    "            if time>course[1]:\n",
    "                time+=heapq.heappop(heap)\n",
    "        return len(heap)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        heap = []\n",
    "        total_time = 0\n",
    "        for course in courses:\n",
    "            if total_time + course[0] <= course[1]:\n",
    "                heapq.heappush(heap, -course[0])\n",
    "                total_time += course[0]\n",
    "            elif len(heap) == 0:\n",
    "                continue\n",
    "            elif heap[0] < -course[0]:\n",
    "                total_time += heap[0] + course[0]\n",
    "                heapq.heappop(heap)\n",
    "                heapq.heappush(heap, -course[0])\n",
    "        return len(heap)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "\n",
    "        ddl = 0\n",
    "        heap = []\n",
    "\n",
    "        for course in courses:\n",
    "            ddl += course[0]\n",
    "            heapq.heappush(heap, -course[0])\n",
    "\n",
    "            if ddl > course[1]:\n",
    "                ddl -= -heapq.heappop(heap)\n",
    "        \n",
    "        return len(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses = sorted(courses, key = lambda x:x[1])\n",
    "        sum = 0\n",
    "        q = list()\n",
    "        for di,si in courses:\n",
    "            print(di)\n",
    "            print(si)\n",
    "            if di + sum <= si :\n",
    "                heapq.heappush(q, -di) #默认小根堆，反过来\n",
    "                sum += di\n",
    "            elif q and -q[0] > di and sum + q[0] + di <= si:\n",
    "                sum -= -q[0] - di\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -di)\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(99999)\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        for d, b in courses:\n",
    "            a = b - d + 1\n",
    "            if a < 1:\n",
    "                continue\n",
    "\n",
    "            arr.append( (b, a, d) )\n",
    "\n",
    "        arr.sort()\n",
    "        que = PriorityQueue()\n",
    "\n",
    "\n",
    "        tasks = PriorityQueue()\n",
    "        for v in arr:\n",
    "            tasks.put(v)\n",
    "\n",
    "        t = 1\n",
    "        cnt = 0\n",
    "        while tasks.qsize():\n",
    "            b, a, d = tasks.get()\n",
    "            if a >= t:\n",
    "                t += d\n",
    "                cnt += 1\n",
    "                que.put( (-d, b, a, d) )\n",
    "\n",
    "            else:\n",
    "                if que.qsize():\n",
    "                    _, bb, aa, dd = que.get()\n",
    "                    if d < dd and a >= t - dd:\n",
    "                        t -= dd\n",
    "                        t += d\n",
    "                        que.put( (-d, b, a, d) )\n",
    "                        tasks.put( (bb, aa, dd) )\n",
    "                    else:\n",
    "                        que.put( (-dd, bb, aa, dd) )\n",
    "\n",
    "        return cnt\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "\n",
    "        q = []\n",
    "        total = 0\n",
    "        for t, d in courses:\n",
    "            if total + t <= d:\n",
    "                # 默认是小跟堆，所以push -t\n",
    "                heapq.heappush(q, -t)\n",
    "                total += t\n",
    "            elif len(q) > 0 and -q[0] > t:\n",
    "                total -= -q[0] - t\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -t)\n",
    "        \n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        q=list()\n",
    "        total=0\n",
    "        for ti,di in courses:\n",
    "            if total+ti<=di:\n",
    "                total+=ti\n",
    "                heapq.heappush(q,-ti)\n",
    "            elif q and -q[0]>ti:\n",
    "                total-=-q[0]-ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q,-ti)\n",
    "            \n",
    "        return len(q)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # import heapq\n",
    "        # total=0\n",
    "        # classes=[]\n",
    "        # courses.sort(key=lambda x:x[1])\n",
    "        # for i in range(len(courses)):\n",
    "        #     time=courses[i][0]\n",
    "        #     total+=time\n",
    "        #     heapq.heappush(classes,-time)\n",
    "        #     if total>courses[i][1]:\n",
    "        #         total+=heapq.heappop(classes)\n",
    "        # return len(classes)\n",
    "        import heapq\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        total=0\n",
    "        classes=[]\n",
    "        for course in courses:\n",
    "            total+=course[0]\n",
    "            heapq.heappush(classes,-course[0])\n",
    "            if total>course[1]:\n",
    "                total+=heapq.heappop(classes)\n",
    "        return len(classes)\n",
    "        # import heapq\n",
    "        # courses = sorted(courses, key = lambda x: x[1])\n",
    "        # print(\"排序后：\",courses)\n",
    "        # d = 0\n",
    "        # heap = []\n",
    "        # for course in courses:\n",
    "        #     print(\"此时的course:\",course)\n",
    "        #     d += course[0]\n",
    "        #     print(\"此时的d:\",d)\n",
    "        #     heapq.heappush(heap, -course[0])\n",
    "        #     print(\"此时的heap:\",heap)\n",
    "        #     if d > course[1]:\n",
    "        #         d += heapq.heappop(heap)\n",
    "        #     print(\"最后的d:\",d)\n",
    "        # return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: (c[1], c[0]))\n",
    "\n",
    "        q = list()\n",
    "        # 优先队列中所有课程的总时间\n",
    "        total = 0\n",
    "\n",
    "        for ti, di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                # Python 默认是小根堆\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        if len(courses) == 1:\n",
    "            return 1 if courses[0][1] >= courses[0][0] else 0\n",
    "\n",
    "        # 先选ddl早的\n",
    "        courses.sort(key=lambda x : (x[1], x[0]))\n",
    "\n",
    "        currentTotalDuration = 0\n",
    "        course_heap = []\n",
    "        for duration, lastDay in courses:\n",
    "            #print(course_heap, (duration, lastDay))\n",
    "            # 当前总时长加上这门课所需时长小于等于这门课ddl,直接加入\n",
    "            if currentTotalDuration + duration <= lastDay:\n",
    "                heapq.heappush(course_heap, -duration)\n",
    "                currentTotalDuration += duration\n",
    "            # 当前总时长加上这门课所需时长大于这门课ddl, 需要将当前课中时长最长的课与这门课进行交换\n",
    "            else:\n",
    "                if course_heap:\n",
    "                    # 当前最长时长的课先出堆\n",
    "                    if -course_heap[0] > duration:\n",
    "                        currentTotalDuration += duration + course_heap[0]\n",
    "                        heapq.heapreplace(course_heap, -duration)\n",
    "\n",
    "        #print(course_heap)\n",
    "        return len(course_heap)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: c[1])\n",
    "\n",
    "        q = list()\n",
    "        # 优先队列中所有课程的总时间\n",
    "        total = 0\n",
    "\n",
    "        for ti, di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                # Python 默认是小根堆\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        nowTime = 0\n",
    "        res = list()\n",
    "        for time, deadline in courses:\n",
    "            if nowTime + time <= deadline:\n",
    "                nowTime += time\n",
    "                res.append(time)\n",
    "            elif res:\n",
    "                res.sort()\n",
    "                if res[-1] > time:\n",
    "                    nowTime += time - res[-1]\n",
    "                    res.pop()\n",
    "                    res.append(time)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "\n",
    "        # Sort courses based on their end days\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        maxHeap = []\n",
    "        currentTime = 0\n",
    "\n",
    "        for duration, endDay in courses:\n",
    "            # Add course to max heap\n",
    "            heapq.heappush(maxHeap, -duration)\n",
    "            currentTime += duration\n",
    "            # If current time exceeds end day, drop the longest course\n",
    "            if currentTime > endDay:\n",
    "                currentTime += heapq.heappop(maxHeap)  # removes the largest duration\n",
    "\n",
    "        return len(maxHeap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:(x[1], x[0]))\n",
    "        h = []\n",
    "        heapq.heapify(h)\n",
    "        time_sum = 0\n",
    "        for duration, ddl in courses:\n",
    "            if time_sum + duration <= ddl:\n",
    "                time_sum += duration\n",
    "                heapq.heappush(h, -duration)\n",
    "            else:\n",
    "                if len(h) > 0 and duration < -h[0]:\n",
    "                    t = -heapq.heappop(h)\n",
    "                    time_sum  = time_sum - t + duration\n",
    "                    heapq.heappush(h, -duration)\n",
    "\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # dead_line升序排序 dead_line相同 cost升序排序\n",
    "        courses.sort(key = lambda x:(x[1], x[0]))\n",
    "        h = []\n",
    "        t = 0\n",
    "        for cost, dead_line in courses:\n",
    "            if t + cost <= dead_line:\n",
    "                t += cost\n",
    "                # 取反插入\n",
    "                heappush(h, -cost)\n",
    "            elif h and cost<-h[0]:\n",
    "                # 弹出取反\n",
    "                t+= cost + heapreplace(h, -cost)\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: (x[1], x[0], x[1] - x[0]))\n",
    "        h = []\n",
    "        today = 0\n",
    "        for duration, last_day in courses:\n",
    "            if today + duration <= last_day:\n",
    "                today += duration\n",
    "                heappush(h, -duration)\n",
    "            elif h and duration < -h[0]:\n",
    "                today += duration\n",
    "                today -= -heapreplace(h, -duration)\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c:c[1])\n",
    "        q=[]\n",
    "        total=0\n",
    "        for [t,d] in courses:\n",
    "            if t+total<=d:\n",
    "                total+=t\n",
    "                heappush(q,-t)\n",
    "            elif q and -q[0]>t:\n",
    "                total-=(-heappushpop(q,-t)-t)\n",
    "        return len(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: (x[1], x[0]))\n",
    "        max_dur_hp = []\n",
    "        cur = 0\n",
    "        for dur, last in courses:\n",
    "            if dur + cur > last:\n",
    "                if max_dur_hp and -max_dur_hp[0] >= dur:\n",
    "                    max_dur = -heapq.heappop(max_dur_hp)\n",
    "                    cur -= max_dur\n",
    "                else:\n",
    "                    continue\n",
    "            heapq.heappush(max_dur_hp, -dur)\n",
    "            cur += dur\n",
    "        return len(max_dur_hp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "            courses.sort(key=lambda x: x[1])\n",
    "\n",
    "            # 用一个优先队列（最大堆）来保存当前已选的课程\n",
    "            current_courses = []\n",
    "            current_time = 0  # 当前学期已经过去的时间\n",
    "\n",
    "            for duration, last_day in courses:\n",
    "                # 如果当前学期还有足够的时间修读这门课\n",
    "                if current_time + duration <= last_day:\n",
    "                    # 将这门课添加到已选课程中\n",
    "                    heapq.heappush(current_courses, -duration)  # 使用负值将最大堆转为最小堆\n",
    "                    current_time += duration\n",
    "                # 如果当前学期没有足够的时间修读这门课，但已选课程中存在持续时间更长的课程，替换掉持续时间最长的课程\n",
    "                elif current_courses and duration < -current_courses[0]:\n",
    "                    current_time += duration + heapq.heappop(current_courses)\n",
    "                    heapq.heappush(current_courses, -duration)\n",
    "\n",
    "            # 最终已选课程的数量即为结果\n",
    "            return len(current_courses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x:(x[1], x[0]))\n",
    "        res = 0\n",
    "        used = 0\n",
    "        heap = []\n",
    "        for duration, ddl in courses :\n",
    "            if heap and used + duration > ddl:\n",
    "                largest = heapq.nsmallest(1, heap)\n",
    "                \n",
    "                if largest[0] >= -duration:\n",
    "                    continue \n",
    "                used -= -heapq.heappop(heap)\n",
    "                res -= 1\n",
    "            if used + duration <= ddl:\n",
    "                heapq.heappush(heap, -duration)\n",
    "                used += duration\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: c[1])\n",
    "\n",
    "        q = list()\n",
    "        # 优先队列中所有课程的总时间\n",
    "        total = 0\n",
    "\n",
    "        for ti, di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                # Python 默认是小根堆\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        queue, total = [], 0\n",
    "        for ti, di in courses:\n",
    "            if total+ti<=di:\n",
    "                total += ti\n",
    "                heapq.heappush(queue, -ti)\n",
    "            elif queue and -queue[0]>ti:\n",
    "                total -= -queue[0] - ti\n",
    "                heapq.heappop(queue)\n",
    "                heapq.heappush(queue, -ti)\n",
    "        return len(queue)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c : c[1])\n",
    "\n",
    "        q = list()\n",
    "        total = 0\n",
    "        for ti,di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                heapq.heappush(q,-ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q,-ti)\n",
    "        \n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # 贪心\n",
    "        heap = []\n",
    "        courses.sort(key=lambda x:x[1])\n",
    "        d = 0 # duration\n",
    "        ans = 0\n",
    "        for duration, lastDay in courses:\n",
    "            heapq.heappush(heap, [-duration, lastDay])\n",
    "            d += duration\n",
    "            while d > lastDay: # 如果当前结束时间大于要求时间，从最小堆移除耗时最长的课程\n",
    "                cur = heapq.heappop(heap)\n",
    "                d += cur[0]\n",
    "        return len(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x : x[1])\n",
    "        curr = 0\n",
    "        count = 0\n",
    "        h = []\n",
    "        ans = 0\n",
    "        for i, j in courses:\n",
    "            count += 1\n",
    "            curr += i\n",
    "            heapq.heappush(h, -i)\n",
    "            while curr > j:\n",
    "                curr += heapq.heappop(h)\n",
    "                count -= 1\n",
    "            ans = max(ans, count)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # 要素有两个：一个持续天数，一个最晚结束时间点\n",
    "        # 按照一维排序，堆维护另一维\n",
    "        # 贪心思路：应该优先学结束时间早\n",
    "        # courses = [[x,y] for x,y in courses if y >= x]\n",
    "        courses.sort(key = lambda x:x[1]) # 按照结束时间从小到大排序\n",
    "        t = 0\n",
    "        pq = []\n",
    "        for dur,last_day in courses:\n",
    "            if t + dur <= last_day:\n",
    "                t += dur\n",
    "                heappush(pq,-dur)\n",
    "            else:\n",
    "                if pq and -pq[0] > dur: # 由于按结束时间从小到大排序，当前结束时间肯定大于之前的结束时间，用当前更短的持续时间替换之前更大的，总时间更短了，肯定能满足\n",
    "                    t += heappop(pq)\n",
    "                    heappush(pq,-dur)\n",
    "                    t += dur\n",
    "        return len(pq)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "            courses.sort(key=lambda x: x[1])\n",
    "\n",
    "            # 用一个优先队列（最大堆）来保存当前已选的课程\n",
    "            current_courses = []\n",
    "            current_time = 0  # 当前学期已经过去的时间\n",
    "\n",
    "            for duration, last_day in courses:\n",
    "                # 如果当前学期还有足够的时间修读这门课\n",
    "                if current_time + duration <= last_day:\n",
    "                    # 将这门课添加到已选课程中\n",
    "                    heapq.heappush(current_courses, -duration)  # 使用负值将最大堆转为最小堆\n",
    "                    current_time += duration\n",
    "                # 如果当前学期没有足够的时间修读这门课，但已选课程中存在持续时间更长的课程，替换掉持续时间最长的课程\n",
    "                elif current_courses and duration < -current_courses[0]:\n",
    "                    current_time += duration + heapq.heappop(current_courses)\n",
    "                    heapq.heappush(current_courses, -duration)\n",
    "\n",
    "            # 最终已选课程的数量即为结果\n",
    "            return len(current_courses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # 1. O(NlogN) sort courses array by lastDay ascendingly\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "\n",
    "        maxHeap = []\n",
    "        t = 0\n",
    "        for duration, lastDay in courses:\n",
    "            t += duration \n",
    "            heappush(maxHeap, -duration)\n",
    "            if t > lastDay:\n",
    "                t += heappop(maxHeap)\n",
    "        return len(maxHeap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c:c[1])\n",
    "        q=list()\n",
    "        total=0\n",
    "        for ti,di in courses:\n",
    "            if total+ti<=di:\n",
    "                total+=ti\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0]>ti:\n",
    "                total-=-q[0]-ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: c[1])\n",
    "\n",
    "        q = list()\n",
    "        # 优先队列中所有课程的总时间\n",
    "        total = 0\n",
    "\n",
    "        for ti, di in courses:\n",
    "            if total + ti <= di:\n",
    "                total += ti\n",
    "                # Python 默认是小根堆\n",
    "                heapq.heappush(q, -ti)\n",
    "            elif q and -q[0] > ti:\n",
    "                total -= -q[0] - ti\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q, -ti)\n",
    "\n",
    "        return len(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda x : x[1])\n",
    "        curr = 0\n",
    "        h = []\n",
    "        for i, j in courses:\n",
    "            curr += i\n",
    "            heapq.heappush(h, -i)\n",
    "            while curr > j:\n",
    "                curr += heapq.heappop(h)\n",
    "        return len(h)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        # 根据最迟完成时间排序\n",
    "        courses.sort(key = lambda x:x[1])\n",
    "\n",
    "        h = [] #需要一个数据结构支持「取出 ttt 值最大的那门课程」，因此我们可以使用优先队列（大根堆）\n",
    "        total = 0 #需要的时间\n",
    "\n",
    "        for d,l in courses:\n",
    "            if total+d<=l:\n",
    "                total += d\n",
    "                heapq.heappush(h,-d)\n",
    "            elif h and -h[0]>d:# 该课程的时间比之前的最长时间要短\n",
    "                # 反悔，撤销之前 duration 最长的课程，改为学习该课程\n",
    "                # 节省出来的时间，能在后面上完更多的课程\n",
    "                total -= (-h[0])\n",
    "                total += d\n",
    "                heapq.heappop(h) #出堆\n",
    "                heapq.heappush(h,-d)\n",
    "        return len(h)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key=lambda c: c[1])  # 按照 last_day 从小到大排序\n",
    "        h = []\n",
    "        day = 0  # 已消耗时间\n",
    "        for duration, last_day in courses:\n",
    "            if day + duration <= last_day:  # 没有超过 last_day，直接学习\n",
    "                day += duration\n",
    "                heappush(h, -duration)  # 加负号变成最大堆\n",
    "            elif h and duration < -h[0]:  # 该课程的时间比之前的最长时间要短\n",
    "                # 反悔，撤销之前 duration 最长的课程，改为学习该课程\n",
    "                # 节省出来的时间，能在后面上完更多的课程\n",
    "                day -= -heapreplace(h, -duration) - duration\n",
    "        return len(h)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        import heapq\n",
    "\n",
    "    # def scheduleCourse(courses):\n",
    "        # 按照截止日期排序\n",
    "        courses.sort(key=lambda x: x[1])\n",
    "        \n",
    "        current_time = 0  # 当前时间\n",
    "        max_heap = []  # 使用最大堆来存储已选课程的持续时间\n",
    "        \n",
    "        for duration, last_day in courses:\n",
    "            if current_time + duration <= last_day:\n",
    "                current_time += duration\n",
    "                heapq.heappush(max_heap, -duration)\n",
    "            elif max_heap and duration < -max_heap[0]:\n",
    "                current_time += duration + heapq.heappop(max_heap)\n",
    "                heapq.heappush(max_heap, -duration)\n",
    "        \n",
    "        return len(max_heap)\n",
    "\n",
    "# 示例用法\n",
    "    # courses = [[9,20],[4,14],[4,10],[6,7],[2,14],[8,10],[6,6],[5,7]]\n",
    "    # print(scheduleCourse(courses))  # 输出 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        maxans = 0\n",
    "        maxcourque = PriorityQueue()\n",
    "        right = 0\n",
    "        ans = 0\n",
    "        courlist = []\n",
    "        for dur, r in courses:\n",
    "            courlist.append((dur, r))\n",
    "        courlist.sort(key=lambda x:x[1])\n",
    "        # print(courlist)\n",
    "        for dur,r in courlist:\n",
    "            if right + dur <= r:\n",
    "                ans += 1\n",
    "                maxans = max(maxans, ans)\n",
    "                right += dur\n",
    "                maxcourque.put((-dur, r))\n",
    "            elif maxcourque.empty() == False:\n",
    "                maxdur, maxr = maxcourque.get()\n",
    "                maxdur = -maxdur\n",
    "                if dur <= maxdur and right-maxdur+dur <= r:\n",
    "                    right -= maxdur\n",
    "                    right += dur\n",
    "                    maxcourque.put((-dur, r))\n",
    "                else:\n",
    "                    maxcourque.put((-maxdur, maxr))\n",
    "        return maxans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        courses.sort(key = lambda x:  x[1])\n",
    "        while courses and courses[0][1] < courses[0][0]:\n",
    "            del courses[0]\n",
    "        if not courses:\n",
    "            return 0\n",
    "        post = courses[0][0]\n",
    "        mark = [courses[0][0]]\n",
    "        res = 1\n",
    "        for content in courses[1:]:\n",
    "            if post + content[0] > content[1]:\n",
    "                mark.sort()\n",
    "                if mark[-1] > content[0] and post + content[0] <= content[1] + mark[-1]:\n",
    "                    t = mark.pop()\n",
    "                    post = post - t + content[0]\n",
    "                    mark.append(content[0])\n",
    "                continue\n",
    "            mark.append(content[0])\n",
    "            post += content[0]\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scheduleCourse(self, courses: List[List[int]]) -> int:\n",
    "        a = []\n",
    "        for c in courses:\n",
    "            a.append((c[1], c[0]))\n",
    "        a.sort()\n",
    "        t = []\n",
    "        ans = 0\n",
    "        sum = 0\n",
    "        for x in a:\n",
    "            if x[1] + sum <= x[0]:\n",
    "                heapq.heappush(t, -x[1])\n",
    "                sum += x[1]\n",
    "                ans += 1\n",
    "            elif t and t[0] + x[1] < 0:\n",
    "                sum += x[1] + t[0]\n",
    "                heapq.heappop(t)\n",
    "                heapq.heappush(t, -x[1])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
